home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 008a / perl40_2.zip / MALLOC.C < prev    next >
C/C++ Source or Header  |  1991-11-28  |  13KB  |  535 lines
  1. /* $RCSfile: malloc.c,v $$Revision: 4.0.1.3 $$Date: 91/11/05 17:57:40 $
  2.  *
  3.  * $Log:    malloc.c,v $
  4.  * Revision 4.0.1.3  91/11/05  17:57:40  lwall
  5.  * patch11: safe malloc code now integrated into Perl's malloc when possible
  6.  *
  7.  * Revision 4.0.1.2  91/06/07  11:20:45  lwall
  8.  * patch4: many, many itty-bitty portability fixes
  9.  *
  10.  * Revision 4.0.1.1  91/04/11  17:48:31  lwall
  11.  * patch1: Configure now figures out malloc ptr type
  12.  *
  13.  * Revision 4.0  91/03/20  01:28:52  lwall
  14.  * 4.0 baseline.
  15.  *
  16.  */
  17.  
  18.  
  19. #ifndef lint
  20. /*SUPPRESS 592*/
  21. static char sccsid[] = "@(#)malloc.c    4.3 (Berkeley) 9/16/83";
  22.  
  23.  
  24. #ifdef DEBUGGING
  25. #define RCHECK
  26. #endif
  27. /*
  28.  * malloc.c (Caltech) 2/21/82
  29.  * Chris Kingsley, kingsley@cit-20.
  30.  *
  31.  * This is a very fast storage allocator.  It allocates blocks of a small
  32.  * number of different sizes, and keeps free lists of each size.  Blocks that
  33.  * don't exactly fit are passed up to the next larger size.  In this
  34.  * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  35.  * This is designed for use in a program that uses vast quantities of memory,
  36.  * but bombs when it runs out.
  37.  */
  38.  
  39.  
  40. #include "EXTERN.h"
  41. #include "perl.h"
  42.  
  43.  
  44. static findbucket(), morecore();
  45.  
  46.  
  47. /* I don't much care whether these are defined in sys/types.h--LAW */
  48.  
  49.  
  50. #define u_char unsigned char
  51. #define u_int unsigned int
  52. #define u_short unsigned short
  53.  
  54.  
  55. /*
  56.  * The overhead on a block is at least 4 bytes.  When free, this space
  57.  * contains a pointer to the next free block, and the bottom two bits must
  58.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  59.  * byte is the size index.  The remaining bytes are for alignment.
  60.  * If range checking is enabled and the size of the block fits
  61.  * in two bytes, then the top two bytes hold the size of the requested block
  62.  * plus the range checking words, and the header word MINUS ONE.
  63.  */
  64. union    overhead {
  65.     union    overhead *ov_next;    /* when free */
  66. #if ALIGNBYTES > 4
  67.     double    strut;            /* alignment problems */
  68. #endif
  69.     struct {
  70.         u_char    ovu_magic;    /* magic number */
  71.         u_char    ovu_index;    /* bucket # */
  72. #ifdef RCHECK
  73.         u_short    ovu_size;    /* actual block size */
  74.         u_int    ovu_rmagic;    /* range magic number */
  75. #endif
  76.     } ovu;
  77. #define    ov_magic    ovu.ovu_magic
  78. #define    ov_index    ovu.ovu_index
  79. #define    ov_size        ovu.ovu_size
  80. #define    ov_rmagic    ovu.ovu_rmagic
  81. };
  82.  
  83.  
  84. #define    MAGIC        0xff        /* magic # on accounting info */
  85. #define OLDMAGIC    0x7f        /* same after a free() */
  86. #define RMAGIC        0x55555555    /* magic # on range info */
  87. #ifdef RCHECK
  88. #define    RSLOP        sizeof (u_int)
  89. #else
  90. #define    RSLOP        0
  91. #endif
  92.  
  93.  
  94. /*
  95.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  96.  * smallest allocatable block is 8 bytes.  The overhead information
  97.  * precedes the data area returned to the user.
  98.  */
  99. #define    NBUCKETS 30
  100. static    union overhead *nextf[NBUCKETS];
  101. extern    char *sbrk();
  102.  
  103.  
  104. #ifdef MSTATS
  105. /*
  106.  * nmalloc[i] is the difference between the number of mallocs and frees
  107.  * for a given block size.
  108.  */
  109. static    u_int nmalloc[NBUCKETS];
  110. #include <stdio.h>
  111. #endif
  112.  
  113.  
  114. #ifdef debug
  115. #define    ASSERT(p)   if (!(p)) botch("p"); else
  116. static
  117. botch(s)
  118.     char *s;
  119. {
  120.  
  121.  
  122.     printf("assertion botched: %s\n", s);
  123.     abort();
  124. }
  125. #else
  126. #define    ASSERT(p)
  127. #endif
  128.  
  129.  
  130. #ifdef safemalloc
  131. static int an = 0;
  132. #endif
  133.  
  134.  
  135. MALLOCPTRTYPE *
  136. malloc(nbytes)
  137.     register unsigned nbytes;
  138. {
  139.       register union overhead *p;
  140.       register int bucket = 0;
  141.       register unsigned shiftr;
  142.  
  143.  
  144. #ifdef safemalloc
  145. #ifdef DEBUGGING
  146.     int size = nbytes;
  147. #endif
  148.  
  149.  
  150. #ifdef MSDOS
  151.     if (nbytes > 0xffff) {
  152.         fprintf(stderr, "Allocation too large: %lx\n", nbytes);
  153.         exit(1);
  154.     }
  155. #endif /* MSDOS */
  156. #ifdef DEBUGGING
  157.     if ((long)nbytes < 0)
  158.         fatal("panic: malloc");
  159. #endif
  160. #endif /* safemalloc */
  161.  
  162.  
  163.     /*
  164.      * Convert amount of memory requested into
  165.      * closest block size stored in hash buckets
  166.      * which satisfies request.  Account for
  167.      * space used per block for accounting.
  168.      */
  169.       nbytes += sizeof (union overhead) + RSLOP;
  170.       nbytes = (nbytes + 3) &~ 3;
  171.       shiftr = (nbytes - 1) >> 2;
  172.     /* apart from this loop, this is O(1) */
  173.       while (shiftr >>= 1)
  174.           bucket++;
  175.     /*
  176.      * If nothing in hash bucket right now,
  177.      * request more memory from the system.
  178.      */
  179.       if (nextf[bucket] == NULL)
  180.           morecore(bucket);
  181.       if ((p = (union overhead *)nextf[bucket]) == NULL) {
  182. #ifdef safemalloc
  183.         fputs("Out of memory!\n", stderr);
  184.         exit(1);
  185. #else
  186.           return (NULL);
  187. #endif
  188.     }
  189.  
  190.  
  191. #ifdef safemalloc
  192. #ifdef DEBUGGING
  193. #  ifndef I286
  194.     if (debug & 128)
  195.         fprintf(stderr,"0x%x: (%05d) malloc %d bytes\n",p+1,an++,size);
  196. #  else
  197.     if (debug & 128)
  198.         fprintf(stderr,"0x%lx: (%05d) malloc %d bytes\n",p+1,an++,size);
  199. #  endif
  200. #endif
  201. #endif /* safemalloc */
  202.  
  203.  
  204.     /* remove from linked list */
  205. #ifdef RCHECK
  206.     if (*((int*)p) & (sizeof(union overhead) - 1))
  207. #ifndef I286
  208.         fprintf(stderr,"Corrupt malloc ptr 0x%x at 0x%x\n",*((int*)p),p);
  209. #else
  210.         fprintf(stderr,"Corrupt malloc ptr 0x%lx at 0x%lx\n",*((int*)p),p);
  211. #endif
  212. #endif
  213.       nextf[bucket] = p->ov_next;
  214.     p->ov_magic = MAGIC;
  215.     p->ov_index= bucket;
  216. #ifdef MSTATS
  217.       nmalloc[bucket]++;
  218. #endif
  219. #ifdef RCHECK
  220.     /*
  221.      * Record allocated size of block and
  222.      * bound space with magic numbers.
  223.      */
  224.       if (nbytes <= 0x10000)
  225.         p->ov_size = nbytes - 1;
  226.     p->ov_rmagic = RMAGIC;
  227.       *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
  228. #endif
  229.       return ((MALLOCPTRTYPE *)(p + 1));
  230. }
  231.  
  232.  
  233. /*
  234.  * Allocate more memory to the indicated bucket.
  235.  */
  236. static
  237. morecore(bucket)
  238.     register int bucket;
  239. {
  240.       register union overhead *op;
  241.       register int rnu;       /* 2^rnu bytes will be requested */
  242.       register int nblks;     /* become nblks blocks of the desired size */
  243.     register int siz;
  244.  
  245.  
  246.       if (nextf[bucket])
  247.           return;
  248.     /*
  249.      * Insure memory is allocated
  250.      * on a page boundary.  Should
  251.      * make getpageize call?
  252.      */
  253.       op = (union overhead *)sbrk(0);
  254. #ifndef I286
  255.       if ((int)op & 0x3ff)
  256.           (void)sbrk(1024 - ((int)op & 0x3ff));
  257. #else
  258.     /* The sbrk(0) call on the I286 always returns the next segment */
  259. #endif
  260.  
  261.  
  262. #ifndef I286
  263.     /* take 2k unless the block is bigger than that */
  264.       rnu = (bucket <= 8) ? 11 : bucket + 3;
  265. #else
  266.     /* take 16k unless the block is bigger than that
  267.        (80286s like large segments!)        */
  268.       rnu = (bucket <= 11) ? 14 : bucket + 3;
  269. #endif
  270.       nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
  271.       if (rnu < bucket)
  272.         rnu = bucket;
  273.     op = (union overhead *)sbrk(1 << rnu);
  274.     /* no more room! */
  275.       if ((int)op == -1)
  276.           return;
  277.     /*
  278.      * Round up to minimum allocation size boundary
  279.      * and deduct from block count to reflect.
  280.      */
  281. #ifndef I286
  282.       if ((int)op & 7) {
  283.           op = (union overhead *)(((int)op + 8) &~ 7);
  284.           nblks--;
  285.       }
  286. #else
  287.     /* Again, this should always be ok on an 80286 */
  288. #endif
  289.     /*
  290.      * Add new memory allocated to that on
  291.      * free list for this hash bucket.
  292.      */
  293.       nextf[bucket] = op;
  294.       siz = 1 << (bucket + 3);
  295.       while (--nblks > 0) {
  296.         op->ov_next = (union overhead *)((caddr_t)op + siz);
  297.         op = (union overhead *)((caddr_t)op + siz);
  298.       }
  299. }
  300.  
  301.  
  302. void
  303. free(mp)
  304.     MALLOCPTRTYPE *mp;
  305. {
  306.       register int size;
  307.     register union overhead *op;
  308.     char *cp = (char*)mp;
  309.  
  310.  
  311. #ifdef safemalloc
  312. #ifdef DEBUGGING
  313. #  ifndef I286
  314.     if (debug & 128)
  315.         fprintf(stderr,"0x%x: (%05d) free\n",cp,an++);
  316. #  else
  317.     if (debug & 128)
  318.         fprintf(stderr,"0x%lx: (%05d) free\n",cp,an++);
  319. #  endif
  320. #endif
  321. #endif /* safemalloc */
  322.  
  323.  
  324.       if (cp == NULL)
  325.           return;
  326.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  327. #ifdef debug
  328.       ASSERT(op->ov_magic == MAGIC);        /* make sure it was in use */
  329. #else
  330.     if (op->ov_magic != MAGIC) {
  331.         warn("%s free() ignored",
  332.             op->ov_magic == OLDMAGIC ? "Duplicate" : "Bad");
  333.         return;                /* sanity */
  334.     }
  335.     op->ov_magic = OLDMAGIC;
  336. #endif
  337. #ifdef RCHECK
  338.       ASSERT(op->ov_rmagic == RMAGIC);
  339.     if (op->ov_index <= 13)
  340.         ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
  341. #endif
  342.       ASSERT(op->ov_index < NBUCKETS);
  343.       size = op->ov_index;
  344.     op->ov_next = nextf[size];
  345.       nextf[size] = op;
  346. #ifdef MSTATS
  347.       nmalloc[size]--;
  348. #endif
  349. }
  350.  
  351.  
  352. /*
  353.  * When a program attempts "storage compaction" as mentioned in the
  354.  * old malloc man page, it realloc's an already freed block.  Usually
  355.  * this is the last block it freed; occasionally it might be farther
  356.  * back.  We have to search all the free lists for the block in order
  357.  * to determine its bucket: 1st we make one pass thru the lists
  358.  * checking only the first block in each; if that fails we search
  359.  * ``reall_srchlen'' blocks in each list for a match (the variable
  360.  * is extern so the caller can modify it).  If that fails we just copy
  361.  * however many bytes was given to realloc() and hope it's not huge.
  362.  */
  363. int reall_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  364.  
  365.  
  366. MALLOCPTRTYPE *
  367. realloc(mp, nbytes)
  368.     MALLOCPTRTYPE *mp;
  369.     unsigned nbytes;
  370. {
  371.       register u_int onb;
  372.     union overhead *op;
  373.       char *res;
  374.     register int i;
  375.     int was_alloced = 0;
  376.     char *cp = (char*)mp;
  377.  
  378.  
  379. #ifdef safemalloc
  380. #ifdef DEBUGGING
  381.     int size = nbytes;
  382. #endif
  383.  
  384.  
  385. #ifdef MSDOS
  386.     if (nbytes > 0xffff) {
  387.         fprintf(stderr, "Reallocation too large: %lx\n", size);
  388.         exit(1);
  389.     }
  390. #endif /* MSDOS */
  391.     if (!cp)
  392.         fatal("Null realloc");
  393. #ifdef DEBUGGING
  394.     if ((long)nbytes < 0)
  395.         fatal("panic: realloc");
  396. #endif
  397. #endif /* safemalloc */
  398.  
  399.  
  400.       if (cp == NULL)
  401.           return (malloc(nbytes));
  402.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  403.     if (op->ov_magic == MAGIC) {
  404.         was_alloced++;
  405.         i = op->ov_index;
  406.     } else {
  407.         /*
  408.          * Already free, doing "compaction".
  409.          *
  410.          * Search for the old block of memory on the
  411.          * free list.  First, check the most common
  412.          * case (last element free'd), then (this failing)
  413.          * the last ``reall_srchlen'' items free'd.
  414.          * If all lookups fail, then assume the size of
  415.          * the memory block being realloc'd is the
  416.          * smallest possible.
  417.          */
  418.         if ((i = findbucket(op, 1)) < 0 &&
  419.             (i = findbucket(op, reall_srchlen)) < 0)
  420.             i = 0;
  421.     }
  422.     onb = (1 << (i + 3)) - sizeof (*op) - RSLOP;
  423.     /* avoid the copy if same size block */
  424.     if (was_alloced &&
  425.         nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP) {
  426. #ifdef RCHECK
  427.         /*
  428.          * Record new allocated size of block and
  429.          * bound space with magic numbers.
  430.          */
  431.         if (op->ov_index <= 13) {
  432.             /*
  433.              * Convert amount of memory requested into
  434.              * closest block size stored in hash buckets
  435.              * which satisfies request.  Account for
  436.              * space used per block for accounting.
  437.              */
  438.             nbytes += sizeof (union overhead) + RSLOP;
  439.             nbytes = (nbytes + 3) &~ 3;
  440.             op->ov_size = nbytes - 1;
  441.             *((u_int *)((caddr_t)op + nbytes - RSLOP)) = RMAGIC;
  442.         }
  443. #endif
  444.         res = cp;
  445.     }
  446.     else {
  447.         if ((res = (char*)malloc(nbytes)) == NULL)
  448.             return (NULL);
  449.         if (cp != res)            /* common optimization */
  450.             bcopy(cp, res, (int)(nbytes < onb ? nbytes : onb));
  451.         if (was_alloced)
  452.             free(cp);
  453.     }
  454.  
  455.  
  456. #ifdef safemalloc
  457. #ifdef DEBUGGING
  458. #  ifndef I286
  459.     if (debug & 128) {
  460.         fprintf(stderr,"0x%x: (%05d) rfree\n",res,an++);
  461.         fprintf(stderr,"0x%x: (%05d) realloc %d bytes\n",res,an++,size);
  462.     }
  463. #  else
  464.     if (debug & 128) {
  465.         fprintf(stderr,"0x%lx: (%05d) rfree\n",res,an++);
  466.         fprintf(stderr,"0x%lx: (%05d) realloc %d bytes\n",res,an++,size);
  467.     }
  468. #  endif
  469. #endif
  470. #endif /* safemalloc */
  471.       return ((MALLOCPTRTYPE*)res);
  472. }
  473.  
  474.  
  475. /*
  476.  * Search ``srchlen'' elements of each free list for a block whose
  477.  * header starts at ``freep''.  If srchlen is -1 search the whole list.
  478.  * Return bucket number, or -1 if not found.
  479.  */
  480. static
  481. findbucket(freep, srchlen)
  482.     union overhead *freep;
  483.     int srchlen;
  484. {
  485.     register union overhead *p;
  486.     register int i, j;
  487.  
  488.  
  489.     for (i = 0; i < NBUCKETS; i++) {
  490.         j = 0;
  491.         for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
  492.             if (p == freep)
  493.                 return (i);
  494.             j++;
  495.         }
  496.     }
  497.     return (-1);
  498. }
  499.  
  500.  
  501. #ifdef MSTATS
  502. /*
  503.  * mstats - print out statistics about malloc
  504.  *
  505.  * Prints two lines of numbers, one showing the length of the free list
  506.  * for each size category, the second showing the number of mallocs -
  507.  * frees for each size category.
  508.  */
  509. mstats(s)
  510.     char *s;
  511. {
  512.       register int i, j;
  513.       register union overhead *p;
  514.       int totfree = 0,
  515.       totused = 0;
  516.  
  517.  
  518.       fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
  519.       for (i = 0; i < NBUCKETS; i++) {
  520.           for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  521.               ;
  522.           fprintf(stderr, " %d", j);
  523.           totfree += j * (1 << (i + 3));
  524.       }
  525.       fprintf(stderr, "\nused:\t");
  526.       for (i = 0; i < NBUCKETS; i++) {
  527.           fprintf(stderr, " %d", nmalloc[i]);
  528.           totused += nmalloc[i] * (1 << (i + 3));
  529.       }
  530.       fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
  531.         totused, totfree);
  532. }
  533. #endif
  534. #endif /* lint */
  535.